/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class sqrtx {
    public static int sqrt(int x) {
        int i=0,j=x;
        while(i<j){
            int mid=i+(j-i)/2;
            long tmp=(long)mid*mid;
            if(tmp==x){
                return mid;
            }else if(tmp<x){
                if((long)(mid+1)*(mid+1)>x){
                    return mid;
                }else{
                    i=mid+1;
                }
            }else{
                j=mid-1;
            }
        }
        return i;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(sqrt(2147395599));
	}

}
